from UserDict import DictMixin

class GraphError(Exception):
	pass

def isbuiltintype(t):
	return isinstance(key, int) or isinstance(key, float) or isinstance(key, complex) or isinstance(key, str)

class Edge(object):
	graph = None
    _s = None  # source vertex
    _t = None  # target vertex
    _undir = True # direction
    _op = None  # edge with opposite direction (only if _undir is True)
  
   def S(e):
        return e._s
    
   def T(e):
        return e._t  
  
   def __getitem__(e, key):
    G = e.graph
    if G.isvertex(key):
      v = G[key]
      if e._s == v: return e._t
      if e._t == v: return e._s
      raise GraphError, "Edge %s hasn't end-vertex %s", str(e), str(v)
    elif G.isedge(key):
      f = G[key]
      if e._s == f._s: return e._s
      if e._s == f._t: return e._s
      if e._t == f._s: return e._t
      if e._t == f._t: return e._t
      raise GraphError, "Edge %s and %s haven't cross-vertex", str(e), str(f)
    else:
      raise GraphError, "Element %s doesn't exist", str(key) 
	
class Vertex(DictMixin):
  graph = None
#  _name = ""
  _neighbors = {}  
  
  def __init__(self, graph, name):
    self.graph = graph
    self._name = name
    
  def __getitem__(v, key):
    try:      
      if isbuiltintype(key):          # if key is name (not instance of Vertex or Edge)
        key = v.graph._names_to_obj[key]   # then we find object with this name
      if isinstance(key, Vertex):    # v[u] returns edge (v,u) 
        return v._neighbors[key]
      elif isinstance(key, Edge):    # v[e] returns opposite vertex of edge e relative to v
        return key[v]  
    except KeyError:            
      raise GraphError, "Vertex or edge %s doesn't exist", str(key)  
    
  def __setitem__(v, key, item):
    G = v.graph
    if G.isset(key):
      if G.isvertex(key):
        u = G[key]
        if G.isvertex(item):
          raise GraphError, "Impossible operation v[v1]=v2"
        if not G.isdiredge(v, u):  # if edge (v,u) doesn't exist
          if not G.isset(item):   # if setted edge doesn't registered
            G.edge(v, u, item)      # then create it
          else:                   
            e = G[item]           # else get it
            del e._s._neighbors[e._t] # delete from old place            
            v._neighbors[u] = e   # change place            
            if e._undir:            # if edge is undirected, then replace the opposite edge too
              e = e._op
              del e._s._neighbors[e._t]
              u._neighbors[v] = e
        else:                     # if edge (v,u) exists
          if not G.isset(item):   # and setted edge doesn't registered
            G.deledge(v, u)          # then delete (v,u)
            G.edge(v, u, item)        # and create the new one
          else:
            e1 = v[u]             # else replace this two edges, hope this code will work
            e2 = G[item]
            if (e1 == e2) or (e1._undir and e1._op == e2):
            	return
             
            v._neighbors[u] = e2  
            #del v._neighbors[u] #
            #if e1._undir:
            #  del u._neighbors[v]
              
            v2 = e2._s
            u2 = e2._t
            
            v2._neighbors[u2] = e1
            
            #del v2._neighbors[u2] #
            #if e2._undir:
            #  del v2._neighbors[u2]
                
            if e1._undir and e2._undir:
              u._neighbors[v] = e2._op
              u2._neighbors[v2] = e1._op    
            elif e1._undir and not e2._undir:
              del u._neighbors[v]
              u2._neighbors[v2] = e1._op
            elif not e1._undir and e2._undir:
              u._neighbors[v] = e2._op
              del u2._neighbors[v2]  
      else:
        e = G[key]
        u = e[v]
        
        
          
        #if e._s == v:
          #u = e._t
        #elif e._t == v:
          #u = e._s
        #else:
          #raise GraphError, "Edge %s hasn't end-vertex %s", str(e), str(v)
           
            
            
        #if G.isset(item):
          #e1 = v[u]
          #e2 = G[item]
          #if e1 == e2 return
          #v._neighbors[u] = e2
          ## replace two edges, pomenyat' mestami dva edga, oni oba uzhe sushestvuyut
        #else:
          ## sozdat novy edge i zamenit im stary, kotory (v,u)
            
      #if self.graph.isset(item):
        ##replace
      #else:
        #self.graph.edge(self,v,item)
    #else:
      #v = self.graph.vertex(key)
      #if self.graph.isset(item):
        ##replace
      #else:
        #self.graph.edge(self,v,item)    
           
      ##if key not in self.graph._names_to_obj:
        ##v = self.graph.vertex(key)
        ##if isbuiltintype(item):
          ##if item not in self.graph._objects:
            ##self.graph.edge(self,v,item)
          ##else:
            ###replace
        ##else:
          ##if item       
        
    #if key in self._neighbors:
      #return self._neighbors[key]
    #raise GraphError, "Vertex %s doesn't exist", str(key)   
    
    
  def keys(self):
    self._neighbors.keys()
     

class Graph(DictMixin):
  _vertices = {}
  _edges = {}
  _names_to_obj = {} # maps names (int, float, complex or str) to objects (Vertex or Edge)
  _objects = set() # sets of objects (Vertex or Edge)
  _dir = False
  
  def isset(self, item):
    if isbuiltintype(item):
      return item in self._names_to_obj
    else:
      return item in self._objects 
      
  def isvertex(self, item):
    if isbuiltintype(item):         # if item is name, then find it in _vertices
      return item in self._vertices
    else:
      return isinstance(item, Vertex) and (item in self._objects)  # else check on type and find it in _objects
      
  def isedge(self, item):
    if isbuiltintype(item):
      return item in self._edges
    else:
      return isinstance(item, Edge) and (item in self._objects)   
      
  def isdiredge(G, source, target):  # returns True if edge (source,taget) exists
    try:
      G[source][target]
    except GraphError:
      return False
    return True  
  
  def __getitem__(self, key):
    if isinstance(key, Vertex) or isinstance(key, Edge):
      return key
    
    if key in self._vertices:
      return self._vertices[key]
    if key in self._edges:
      return self._edges[key]
    raise GraphError, "Vertex or edge %s doesn't exist", str(key)
  
  def __setitem__(self, key, item):
    if key in self._vertices:
      #rename
    else:
      raise GraphError, "Vertex %s doesn't exist", str(key)
      
  def keys(self):
    self._vertices.keys()
      
  def vertex(self, name):
    if name in self._vertices:
		  raise GraphError, 'Duplicate vertex %s', str(name)
    else:
      v = Vertex(self, name)
      self._vertices[name] = v
      self._names_to_obj[name] = v
      self._objects.add(v)
  
  def edge(self, u, v, name, dir=None):
    if name in self._edges:
		  raise GraphError, 'Duplicate edge %s', str(name)
    else:
      if dir is None:
        dir = self._dir
        
      edge = Edge(u, v, name, dir)
      self._edges[name] = edge
      self._vertices[u][v] = edge
      self._objects.add(edge)
      
